package mao.algorithm.redbook.demo29_9;

import java.util.ArrayList;
import java.util.List;

public class WeightedGraph extends Graph{
	private List<List<WeightedEdge>> edges = new ArrayList<>();
	public WeightedGraph(int nodeNumber) {
		super(nodeNumber);
		
	}
	
	public  void addEdge(int u,int v,int weight) {
		while(edges.size() <= u){
		   edges.add(new ArrayList<WeightedEdge>());
		}
		while(edges.size() <= v){
		  edges.add(new ArrayList<WeightedEdge>());
		}
		edges.get(u).add(new WeightedEdge(u,v,weight));
		edges.get(v).add(new WeightedEdge(v,u,weight));
	}
	public WeightTree getMinmunSpaningTree(int source){
		List<Integer> T = new ArrayList<Integer>();
		int[] cost = new int[NUMBER_OF_NODE];
		int[] parent = new int[NUMBER_OF_NODE];
		int totalCost = 0;
		for (int i=0;i<NUMBER_OF_NODE;i++) {
			cost[i]=Integer.MAX_VALUE;
		}
		cost[source] = 0;
		for (int i=0;i<NUMBER_OF_NODE;i++) {
			parent[i]=-2;
		}
		parent[source]=-1;
		int u = source ;
	
		while(T.size() < NUMBER_OF_NODE){
			int minCost = Integer.MAX_VALUE;
		
			for(int i= 0;i<NUMBER_OF_NODE;i++){
				if(!T.contains(i) && minCost>cost[i]){
					minCost = cost[i];
					u=i;
				}
			}
			T.add(u);
			totalCost+=cost[u];
			
			
			List<WeightedEdge> list = edges.get(u);
			for(int i = 0;i<list.size();i++){
				WeightedEdge edge = list.get(i);
				if(!T.contains(edge.getV()) && edge.getWeight() < cost[edge.getV()]){
					cost[edge.getV()] = edge.getWeight();
					parent[edge.getV()] = u;
				}
			}
			
		}
		
		return new WeightTree(parent,cost,totalCost);
	}
	
    public static class WeightTree extends Graph.Tree{
    	private int[] cost ; 
    	private int totalCost ;
		public WeightTree(int[] parent,int[] cost, int totalCost) {
			super(parent);
			this.cost = cost.clone();
			this.totalCost = totalCost;
		}
		public void printTree(){
			for(int i=0;i<parent.length;i++){
				if(parent[i] != -1 && parent[i]!= -2){
					System.out.println("("+parent[i]+","+i+","+cost[i]+")");
				}
			}
		}
		public void printTotalWeight(){
			System.out.println(totalCost);
		}
	}

	public void printEdges() {
		for (List<WeightedEdge> list : edges) {
			  for (WeightedEdge weightedEdge : list) {
				System.out.println(weightedEdge);
			}
		}
		
	}
	

}
